/*
 * @lc app=leetcode.cn id=503 lang=typescript
 *
 * [503] 下一个更大元素 II
 */

// @lc code=start

//  思路：单调栈
//  栈里面需要保存元素在数组中的下标，因为需要根据下标修改 res。

//  复杂度：O(n) O(n)

function nextGreaterElements(nums: number[]): number[] {
    const len = nums.length
    const res = new Array(len).fill(-1)
    const stack = []

    for (let i = 0; i < 2 * len - 1; i++) {
        // 如果有更靠前的更大元素，那么这些位置将被提前弹出栈
        while (stack.length && nums[stack[stack.length - 1]] < nums[i % len]) {
            res[stack.pop()!] = nums[i % len]
        }
        stack.push(i % len)
    }
    return res
};
// @lc code=end

console.log(nextGreaterElements([1, 2, 1]))
